#include <iostream>
#include <utility>
#include <cassert>

// #define PRINT_INFO

namespace stl_self
{
    template <typename Type>
    class vector
    {
    public:
        typedef Type value_type;
        typedef Type *iterator;
        typedef const Type *const_iterator;

    private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storage;

    public:
        iterator begin() { return _start; }
        iterator end() { return _finish; }
        const_iterator begin() const { return _start; }
        const_iterator end() const { return _finish; }

    public:
        vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
        {
#ifdef PRINT_INFO
            std::cout << "vector()" << std::endl;
#endif
        }
        vector(size_t n, const Type &value = Type())
            : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
        {
            // 扩容
            reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                push_back(value);
            }
#ifdef PRINT_INFO
            std::cout << "vector(size_t n, const Type &value = Type())" << std::endl;
#endif
        }

        vector(const vector<Type> &v) // 拷贝构造
            : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
        {
            reserve(v.capacity());
            _start = new Type[v.capacity()];
            for (size_t i = 0; i < v.size(); ++i)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _end_of_storage = _start + v.capacity();
#ifdef PRINT_INFO
            std::cout << "vector(const vector<Type> &v)" << std::endl;
#endif
        }

        vector(vector<Type> &&v) // 移动构造
        {
            swap(v);
#ifdef PRINT_INFO
            std::cout << "vector(vector<Type> &&v)" << std::endl;
#endif
        }

        ~vector()
        {
            delete[] _start;
            _start = _finish = _end_of_storage = nullptr;
#ifdef PRINT_INFO
            std::cout << "~vector()" << std::endl;
#endif
        }

        vector<Type> &operator=(const vector<Type> &v) // 拷贝赋值
        {
            if (this != &v)
            {
                if (_start != nullptr)
                {
                    delete[] _start;
                    _start = _finish = _end_of_storage = nullptr;
                }
                _start = new Type[v.capacity()];
                for (size_t i = 0; i < v.size(); ++i)
                {
                    _start[i] = v._start[i];
                }
                _finish = _start + v.size();
                _end_of_storage = _start + v.capacity();
            }

#ifdef PRINT_INFO
            std::cout << "vector<Type> &operator=(const vector<Type> &v)" << std::endl;
#endif
        }

        vector<Type> &operator=(vector<Type> &&v) // 移动赋值
        {
            if (this != &v)
            {
                swap(v);
            }
#ifdef PRINT_INFO
            std::cout << "vector<Type> &operator=(vector<Type> &&v)" << std::endl;
#endif
        }

        size_t capacity() const { return _end_of_storage - _start; }
        size_t size() const { return _finish - _start; }
        Type &operator[](const size_t &pos)
        {
            assert(pos < size());
            return _start[pos];
        }
        const Type &operator[](const size_t &pos) const
        {
            assert(pos < size());
            return _start[pos];
        }
        bool empty() { return _start == _finish; }

        void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t len = size();
                iterator tmp = new Type[n];
                if (_start != nullptr)
                {
                    for (size_t i = 0; i < len; ++i)
                    {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }
                _start = tmp;
                _finish = _start + len;
                _end_of_storage = _start + n;
            }
        }

        void resize(size_t n, Type value = Type())
        {
            if (n < size())
            {
                _finish = _start + n;
            }
            else
            {
                if (n > capacity())
                {
                    reserve(n);
                }
                // size() <= n < capacity()
                while (_finish != _start + n)
                {
                    *_finish = value;
                    ++_finish;
                }
            }
        }

        void push_back(const Type &value)
        {
            if (_finish == _end_of_storage)
            {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = value;
            ++_finish;
        }

        // void push_back(Type &&value)
        // {
        //     if(_finish == _end_of_storage)
        //     {
        //         reserve(capacity() == 0 ? 4 : capacity() * 2);
        //     }
        //     *_finish = value;
        //     ++_finish;
        // }

        void pop_back()
        {
            assert(!empty());
            --_finish;
        }

        iterator insert(iterator pos, const Type &value)
        {
            assert(pos >= _start && pos <= _finish);
            if (_finish == _end_of_storage) // 扩容
            {
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : capacity() * 2);
                pos = _start + len;
            }

            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
            *pos = value;
            ++_finish;
            return pos;
        }

        iterator erase(iterator pos)
        {
            assert(pos >= _start && pos <= _finish);
            iterator start = pos + 1;
            while (start != _finish)
            {
                *(start - 1) = *start;
                ++start;
            }
            --_finish;
            return pos;
        }

        void swap(vector<Type> &v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_end_of_storage, v._end_of_storage);
        }

        void show() const // 打印
        {
            for (auto &x : *this)
            {
                std::cout << x << " ";
            }
            std::cout << std::endl;
        }
    };

} // namespace my_stl
